
// 139.单词拆分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //动态规划 , 以i位置为结尾记录[0 , i] 是否可以有字典凭借而成
        unordered_set<string> st;
        for(auto& str : wordDict) st.insert(str);

        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0] = true;
        s = " " + s;
        for(int i = 1; i <= n ; i++)
        {
            for(int j = 1 ; j <= i ; j++)
            {
                if( dp[j-1] && st.count(s.substr(j,i - j + 1))) 
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};